//
//  Offer_01.swift
//  LeetCode
//
//  Created by migu on 2020/9/2.
//  Copyright © 2020 LBB. All rights reserved.
//  数组中重复的数字
//  在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
//  数组长度限制:2 <= n <= 100000

import Foundation
class FindRepeatNumber {
    func findRepeatNumber(_ nums: [Int]) -> Int {
        //暴力解
//        for i in 0..<nums.count {
//            let m:Int = nums[i]
//            for j in i+1..<nums.count {
//                let n:Int = nums[j]
//                if m == n {
//                    return nums[i]
//                }
//            }
//        }
        //优化解
//        let repetitionNums:NSMutableArray = []
//        for i in 0..<nums.count {
//            if !repetitionNums.contains(nums[i]) {
//                repetitionNums .add(nums[i])
//            } else {
//                return nums[i]
//            }
//        }
        //最优解
        var nums = nums
        for i in 0..<nums.count {
            while i != nums[i] {
                if nums[i] == nums[nums[i]] {
                    return nums[i]
                } else {
                    //数组中两个元素交换位置
                    nums.swapAt(i, nums[i])
                }
            }
        }
        
        return -1
    }
}
